package hard;

/**
 * @Description :给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 *              算法的时间复杂度应该为 O(log (m+n)) 。
 * @Author : machong
 * @Date : 2022/3/30 1:21
 * @Version : 1.0
 **/
public class leetCode04_findMedianSortedArrays {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        /**
         * 方法一：使用归并的方式，合并两个有序数组，得到一个大的有序数组。大的有序数组的中间位置的元素，即为中位数。时间复杂度O(m+n)，
         * 空间复杂度O(m+n)，---待优化
         */
//        int resLen = nums1.length+nums2.length;
//        int[] resultList = new int[resLen];
//        double result ;
//        int pointer1=0,pointer2=0;
//        for (int i = 0; i < resLen; i++) {
//            if (pointer1 == nums1.length || pointer2 == nums2.length){
//                resultList[i] = pointer1 == nums1.length ? nums2[pointer2++] : nums1[pointer1++];
//            }else if (nums1[pointer1]<=nums2[pointer2]){
//                resultList[i] = nums1[pointer1];
//                pointer1++;
//            }else {
//                resultList[i] = nums2[pointer2];
//                pointer2++;
//            }
//        }
//        if (resultList.length % 2 != 0){
//            result = (double)resultList[resLen/2];
//        }else {
//            result = ((double)resultList[resultList.length / 2 -1] + (double)resultList[(resultList.length ) / 2]) /2;
//        }
//        return result;

        /**
         * 方法二：二分思想  时间复杂度O(log(m+n)),空间复杂度O（1）
         */
        int n = nums1.length;
        int m = nums2.length;
        //合并处理两数组之和为奇偶的情况，奇数个时left和right相等，偶数个时right-left=1
        int left = (n + m +1)/2;
        int right = (n + m +2)/2;
        int leftKthNum = getKth(nums1,0,n-1,nums2,0,m-1,left);
        int rightKthNum = getKth(nums1,0,n-1,nums2,0,m-1,right);
        return (leftKthNum +rightKthNum) / 2.0;
    }

    /**
     * @param num1      数组1
     * @param start1    数组1的开始位置
     * @param end1      数组1的结束位置
     * @param num2      数组2
     * @param start2    数组2的开始位置
     * @param end2      数组2的结束位置
     * @param kth       第k个
     */
    public static int getKth(int[] num1,int start1,int end1,int[] num2,int start2,int end2,int kth){
        //当前[start1..end1] 和 [start2...end2]的长度
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //始终保持num1的长度短
        if (len1 > len2){
            return getKth(num2,start2,end2,num1,start1,end1,kth);
        }
        //数组1为空时，直接取start2 + kth -1即为kth大的数
        if (len1 == 0){
            return num2[start2 + kth -1];
        }
        //kth经剩下1个时，说明找到了
        if (kth == 1){
            return Math.min(num1[start1],num2[start2]);
        }
        //每次取kth的一半 计算新的i和j开始二分
        int i = start1 + Math.min(len1,kth/2) -1;
        int j = start2 + Math.min(len2,kth/2) -1;
        //如果num1[i] > num2[j]去掉[start2...j]的部分，反之，去掉[start1...i]的部分
        if (num1[i] > num2[j]){
            return getKth(num1,start1,end1,num2,j + 1 ,end2,kth-(j - start2 +1));
        }else {
            return getKth(num1,i + 1,end1,num2,start2,end2,kth-(i - start1 +1));
        }
    }
}
